#pragma once
#include <assert.h>

namespace lw
{
	template<class T>
	struct ListNode
	{
		T _data;
		ListNode<T>* _prev;
		ListNode<T>* _next;
		ListNode(const T& val = T()) :_data(val), _prev(nullptr), _next(nullptr) { }
		ListNode(T&& val) : _data(std::move(val)), _prev(nullptr), _next(nullptr) { }
		template<class ...Args>
		ListNode(Args&& ... args)
			:_data(std::forward<Args>(args)...), _prev(nullptr), _next(nullptr)
		{}
	};

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		Ref operator*() 
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}
		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
		void init()
		{
			_head = new Node();
			_head->_prev = _head;
			_head->_next = _head;
		}
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		const_iterator end() const
		{
			return _head;
		}
		list() 
		{
			init();
		}
		list(size_t n, const T& val = T()) 
		{
			init();
			for (int i = 0; i < n; i++)
				push_back(val);
		}
		list(int n, const T& val = T()) 
		{
			init();
			for (int i = 0; i < n; i++)
				push_back(val);
		}
		list(const std::initializer_list<T>& lt)
		{
			init();
			for (const auto& e : lt)
				push_back(e);
		}
		template<class InputIterator>
		list(InputIterator first, InputIterator last) 
		{
			init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		list(const list<T>& lt) 
		{
			init();
			for (const auto& e : lt)
				push_back(e);
		}
		list(list<T>&& lt) 
		{
			swap(lt);
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			_size = 0;
		}
		list<T>& operator=(const list<T>& lt) 
		{
			if (this != &lt)
			{
				list<T> tmp(lt);
				swap(tmp);
			}
			return *this;
		}
		list<T>& operator=(list<T>&& lt) 
		{
			swap(lt);
			return *this;
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		void clear() 
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		iterator insert(iterator pos, const T& val) 
		{
			Node* curr = pos._node;
			Node* prev = curr->_prev;
			Node* newnode = new Node(val);
			// prev newnode curr
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = curr;
			curr->_prev = newnode;

			++_size;
			return newnode;
		}
		iterator insert(iterator pos, T&& val)
		{
			Node* curr = pos._node;
			Node* prev = curr->_prev;
			Node* newnode = new Node(std::move(val));
			// prev newnode curr
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = curr;
			curr->_prev = newnode;

			++_size;
			return newnode;
		}
		iterator erase(iterator pos) 
		{
			Node* curr = pos._node;
			Node* prev = curr->_prev, * next = curr->_next;
			prev->_next = next;
			next->_prev = prev;

			--_size;
			delete curr;
			return next;
		}
		template<class ...Args>
		iterator emplace(iterator pos, Args&& ... args)
		{
			Node* curr = pos._node;
			Node* prev = curr->_prev;
			Node* newnode = new Node(std::forward<T>(args)...);
			// prev newnode curr
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = curr;
			curr->_prev = newnode;

			++_size;
			return newnode;
		}
		template<class ...Args>
		void emplace_back(Args&& ...args)
		{
			insert(end(), std::forward<Args>(args)...);
		}
		template<class ...Args>
		void emplace_front(Args&& ...args)
		{
			insert(begin(), std::forward<Args>(args)...);
		}
		void push_back(const T& val) 
		{
			insert(end(), val);
		}
		void push_front(const T& val) 
		{
			insert(begin(), val);
		}
		void push_back(T&& val)
		{
			insert(end(), std::move(val));
		}
		void push_front(T&& val)
		{
			insert(begin(), std::move(val));
		}
		void pop_back() 
		{
			erase(--end());
		}
		void pop_front() 
		{
			erase(begin());
		}
		bool empty() const 
		{
			return _size == 0;
		}
		size_t size() const 
		{
			return _size;
		}
	private:
		Node* _head = nullptr;
		size_t _size = 0;
	};

	void testList1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int> lt2 = lt;
		for (const auto& e : lt)
			std::cout << e << " ";
		std::cout << std::endl;
		for (const auto& e : lt2)
			std::cout << e << " ";
		std::cout << std::endl;

		list<int> lt3(10, 4);
		list<int> lt4{ 10, 20, 30, 40, 50 };
		for (const auto& e : lt3)
			std::cout << e << " ";
		std::cout << std::endl;
		for (const auto& e : lt4)
			std::cout << e << " ";
		std::cout << std::endl;
	
		lt3 = lt4;
		for (const auto& e : lt3)
			std::cout << e << " ";
		std::cout << std::endl;
		for (const auto& e : lt4)
			std::cout << e << " ";
		std::cout << std::endl;

	}

	void testList2()
	{
		list<int> lt{ 10, 20, 30, 40, 11 };
		lt.push_front(1000);
		for (const auto& e : lt)
			std::cout << e << " ";
		std::cout << std::endl;

		lt.pop_back();
		for (const auto& e : lt)
			std::cout << e << " ";
		std::cout << std::endl;

		lt.push_back(110);
		for (const auto& e : lt)
			std::cout << e << " ";
		std::cout << std::endl;

		lt.erase(++lt.begin());
		for (const auto& e : lt)
			std::cout << e << " ";
		std::cout << std::endl;

		lt.insert(++lt.begin(), 17);
		for (const auto& e : lt)
			std::cout << e << " ";
		std::cout << std::endl;
	}
	void func(const list<int>& lt)
	{
		for (auto& e : lt)
			std::cout << e << " ";
		std::cout << std::endl;
	}
	void testList3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		func(lt);
	}
}